package sort;

import comment.Comment;

/**
 *create by tbj
 */
	//寻找一个数组中第k大的数
public class SelectNum {
	private static int partition(int[] a,int l,int r){
		int v=a[l];
		int j=l;
		for(int i=l+1;i<=r;i++){
			if(a[i]<v){
				Comment.swapIntArr(a, i, j+1);
				j++;
			}
		}
		Comment.swapIntArr(a, j, l);
		return j;
	}
	private static int _select(int[] a,int l,int r,int num){
		if(l==r){
			return a[l];
		}
		int p=partition(a,l,r);
		if(p==num){
			return a[p];
		}else if(p<num){
			return _select(a, p+1, r, num);
		}else{
			return _select(a, l, p-1, num);
		}
	}
	public static int select(int[] a,int num){
		int n=a.length;
		return _select(a,0,n-1,num-1); //我们找的第一大，其实数组结果给我们第二大的、所以减1
	}
	public static void main(String[] args) {
		int[] a=Comment.getSortIntArr();
		System.out.println("寻找数组中第n大的数，请输入1到"+a.length);
		System.out.println(SelectNum.select(a, 2));
	}
}
